/*
 * Hash.h
 *
 *  Created on: 2011-7-8
 *      Author: gexiao
 */
/*
 * General purpose hash table, used for finding classes,methods, etc.
 *
 * When the number of elements reaches a certain percentage of the table's
 * capacity, the table will be resized.
 */
#ifndef HASH_H_
#define HASH_H_
#include "Common.h"

#include <pthread.h>

/*
 * Compare a hash entry with a "loose" item after their hash values match.
 * Returns {<0,0,>0} depending on ordering of items (same semantics
 * as strcmp()).
 */
typedef int (*HashCompareFunc)(const void* tableItem, const void* looseItem);

/*
 * This function will be used to free entries in the table. This can be
 * NULL if no free is required, free(), or a custom function.
 */
typedef void (*HashFreeFunc)(void* ptr);

/*
 * One entry in the hash table. "data" values are expected to be (or have
 * the same characteristics as) valid pointers. In particular, a NULL
 * value for "data" indicates an empty slot, and HASH_TOMBSTONE indicates
 * a no-longer-used slot that must be stepped over during probing.
 *
 * Attempting to add a NULL or tombstone value is an error.
 *
 * When an entry is released, we will call (HashFreeFunc)(entry->data).
 */
typedef struct HashEntry {
	u4 hashValue;
	void* data;
} HashEntry;

#define HASH_TOMBSTONE ((void*) 0xcbcacccd) //invalid ptr value
/*
 * Expandable hash table.
 *
 * This structure should be considered opaque.
 */
typedef struct HashTable {
	int tableSize; //must be power of 2
	int numEntries; //current #of "live" entries
	int numDeadEntries; //current #of tombstone entries
	HashEntry* pEntries; //array on heap
	HashFreeFunc freeFunc;
	pthread_mutex_t lock;
} HashTable;

/*
 * Create and initialize a HashTable structure,using "initialSize" as
 * a basic for the initial capacity of the table. (The actual initial
 * table size may be adjusted upward.) If you know exactly how many
 * elements the table will hold, pass the result from dvmHashSize() in.)
 *
 * Returns "false" if unable to allocate the table.
 */
HashTable* dvmHashTableCreate(size_t initialSize, HashFreeFunc freeFunc);

/*
 * Exclusive access. Important when adding items to a table, or when
 * doing any operations on a table that could be added to by another thread.
 */
INLINE void dvmHashTableLock(HashTable* pHashTable) {
	dvmLockMutex(&pHashTable->lock);
}
INLINE void dvmHashTableUnlock(HashTable* pHashTable) {
	dvmUnlockMutex(&pHashTable->lock);
}

/*
 * Look up an entry in the table, possibly adding it if it's not there.
 *
 * If "item" is not found, and "doAdd" is false,NULL is returned.
 * Otherwise, a pointer to the found or added item is returned. (You can
 * tell the difference by seeing if return value==item).
 *
 * An "add" operation may cause the entries table to be reallocated.
 */
void* dvmHashTableLookup(HashTable* pHashTable, u4 itemHash, void* item,
		HashCompareFunc cmpFunc, bool doAdd);

/*
 * Remove an item from the hash table, given its "data" pointer. Does not
 * invoke the "free" function; just detaches it from the table.
 */
bool dvmHashTableRemove(HashTable* pHashTable, u4 hash, void* item);
#endif /* HASH_H_ */

